import java.util.Arrays;

/**
 * Created by IntelliJ
 * Author:熊磊
 */
public class FibonacciSearch {
    public static int maxSize = 20;

    public static void main(String[] args) {
        int arr[] = {1, 8, 10, 89, 1000, 1234};
        System.out.println(fibSearch(arr, 1000));
    }

    public static int[] fib() {
        int[] f = new int[maxSize];
        f[0] = 1;
        f[1] = 1;
        for (int i = 2; i < maxSize; i++) {
            f[i] = f[i - 1] + f[i - 2];
        }
        return f;
    }

    public static int fibSearch(int[] a, int value) {
        int low = 0;
        int high = a.length - 1;
        int k = 0;
        int mid = 0;
        int[] fib = fib();

        //找到一个斐波那契值,让这个值为临时数组的长度，且改值一定要大于或等于原来的长度
        while (high+1 > fib[k]) {
            k++;
        }
        //此时的新数组的长度是一个斐波那契值且大于或等于原数组的值
        int[] temp = Arrays.copyOf(a, fib[k]);
        //大于原数组的部分要用该数组里最大的一个值进行填充
        //i不能从high+1开始,如果恰巧两个;'
        // 数组长度相等会越界
        for (int i = high; i < temp.length; i++) {
            temp[i] = a[high];
        }

        //因为数组的长度为f(k) 所以数组的索引为 0 ~ f(k)-1
        //f(k) -1 = f(k-1)-1 +f(k-2)-1 +1
        //把f(k-1)-1 当做左边的数据个数,f(k-2)-1当做右边的数据个数
        while (low <= high) {
            //此时fib[k]=数组长度,fib[k-1]为黄金比例比较高的部分
            mid = low + fib[k - 1] -1 ;
            //fib[k-1] 的长度大于 fib[k-2]的长度
            //当你要找的值小于temp[mid]时,代表你需要把mid左边的长度进行一个黄金分割
            //此时需要将f[k-1]分为f[k-2]+f[k-3]
            if (value < temp[mid]) {
                high = mid - 1;
                k--;
            } else if (value > temp[mid]) {
                low = mid + 1;
                k -= 2;
            } else {
                //high指针最大是原来的数组大小,所以mid有可能大于high
                if (mid <= high) {
                    return mid;
                } else {
                    return high;
                }
            }
        }
        return -1;
    }
}
